package code.starivan.leetcode;

import code.starivan.leetcode.common.ListNode;

/**
 * Created by Ivan on 2015/10/27.
 */

/*
Remove all elements from a linked list of integers that have value val.

        Example
        Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
        Return: 1 --> 2 --> 3 --> 4 --> 5

        Credits:
        Special thanks to @mithmatt for adding this problem and creating all test cases.

*/

public class N203_RemoveLinkedListElements {
    public static void test(){
        ListNode head=ListNode.construct(new int[]{6,6,4});
        head.printList();
        ListNode retHead=new N203_RemoveLinkedListElements().removeElements(head,6);
        retHead.printList();
    }

    public ListNode removeElements(ListNode head, int val) {
        if(head==null){
            return null;
        }

        ListNode node=head;
        ListNode newHead=head;
        ListNode pre=null,next=null;
        while (node!=null){
            next=node.next;
            if(node.val==val){
                if(node==newHead){
                    newHead=next;
                    pre=null;
                }

                if(pre!=null){
                    pre.next=next;
                }

                node.next=null;
            }else{
                pre=node;
            }

            node=next;
        }

        return newHead;
    }


}
